package com.kaigejava.queue.circlearrayqueue;

/**
 * @author kaigejava
 * 循环队列类
 * 用数组模拟循环队列
 * 分析：
 * 单向队列只能使用一次。效率和复用率都不高。可以将队列设置成环形队列。
 * 环形队列可以通过【取模的方式来实现】
 * 思路：
 * 1：front(队首)变量的含义做一个调整：
 *  front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素了。初始值为0
 *  （在原来队列的时候，front初始值是-1）
 * 2：rear的含义调整：
 *  rear指向队列的最后一个元素的下一个位置。因为希望空出一个空间作为约定。初始值为0
 * 3：当队列满的时候，条件 (rear+1)%maxSize = front
 * (原来队列判断满的时候是：rear = maxSize -1 )
 * 4：队列为空的条件，rear == front的时候
 * 5：循环队列后，队列中有效数据的个数就是：(rear + maxSize - front)%maxsize //rear = 1 front = 0
 *
 * 模拟队列的功能：
 * 1：向队列中添加数据；
 * 2：从队列中获取数据
 * 3：队列是否为空
 * 4：队列是否已经满了
 * 5：显示队列头数据
 */
public class CircleArrayQueue {
    /**
     * 队列的最大值.因为要预留一个空的位置。所以，有效数量最大值=maxSize -1
     */
    private int maxSize;

    /**
     * 队列头
     */
    private int front;

    /**
     * 对列尾部
     */
    private  int rear;

    /**
     * 存放数据的容器
     */
    private int [] arr;

    public CircleArrayQueue (int maxSize){
        this.maxSize = maxSize;
        arr = new int [maxSize];
    }

    /**
     * 判断队列是否已经满了
     * 判断依据：rear == front
     * 又因为real指向了队列最后一个的下一个,而且是循环队列
     * 所以real+1 取 maxSize == front 表示已经满了
     * @return
     */
    public boolean isFull(){
        boolean b = (rear +1) % maxSize == front;
        return b;
    }

    /**
     * 判断是否为空队列
     * 因为初始值 front 和 rear都是0
     * @return
     */
    public boolean isEmpty(){
        return rear == front;
    }

    /**
     * 入队
     * @param n
     */
    public void addQueue(int n){
        if(isFull()){
            System.out.println("队列已经满了。不能继续添加了");
            return;
        }
        //这里队尾不用++了，因为real 从0开始的。队尾的值直接就等于需要添加的值了
        arr[rear] = n;
        //将队尾++。因为是循环队列。所以，需要取模
        rear = (rear+1)%maxSize;
    }

    /**
     * 出队
     * 思路：
     * 从front取数据，front需要向后移(这是原来的)，但是这里是循环队列。所以需要取模
     * 因为front循环会变化的。所以，先要使用变量保存。然后front在++
     * @return
     */
    public int getQueue(){
        if(isEmpty()){
            System.out.println("队列为空。不能继续获取到数据了");
            throw  new RuntimeException("队列为空");
        }
        //
        int frontVal = arr[front];
        //循环队列。头指针++后 取模
        front = (front+1)%maxSize;
        return frontVal;
    }


    /**
     * 显示队列中所有的数据
     * 思考：
     * 1：循环的开始位置是什么？是0吗？当然不是。因为是循环队列。所以，起始位置应该是front
     * 2：循环多少次呢？是maxSize吗？应该是当前队列中的是数量.那么队列中数量可以：arr.length吗？当然不可以了。因为是循环队列。
     *  比如：rear = 2
     *  front = 1
     *  maxSize = 3
     *  请问，在这种情况下，队列的有效数据有几个呢？
     *  假如还没循环的话，length应该= 1
     *  但是如果循环了呢？是不是要取模。那么取模怎么取值呢？
     *  应该是：( rear + maxSize - front ) % maxSize;
     *  所以，应该循环几次呢？应该循环次数是：front+size次
     *
     */
    public void showAll(){
        if(isEmpty()){
            System.out.printf("队列为空。不能继续获取到数据了");
            throw  new RuntimeException("队列为空");
        }
        int size = getSize();
        System.out.println("队列的有效长度为:"+size);
        //从front开始遍历，遍历的长度
        for (int i = front; i < front +size; i++) {
            System.out.printf("arr[%d] = %d \n ",i%maxSize,arr[i%maxSize]);
        }
    }


    /**
     * 偷窥
     * @return
     */
    public int hearQueue(){
        if(isEmpty()){
            System.out.println("队列为空。不能继续获取到数据了");
            throw  new RuntimeException("队列为空");
        }
        return  arr[front];
    }

    /**
     * 获取队列中有效个数 = 队尾+maxSize - 对头 % 总数
     * @return
     */
    public int getSize(){
        return (rear + maxSize - front) % maxSize;
    }
}
